//The MIT License
//
//Copyright (c) 2009 nodchip
//
//Permission is hereby granted, free of charge, to any person obtaining a copy
//of this software and associated documentation files (the "Software"), to deal
//in the Software without restriction, including without limitation the rights
//to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
//copies of the Software, and to permit persons to whom the Software is
//furnished to do so, subject to the following conditions:
//
//The above copyright notice and this permission notice shall be included in
//all copies or substantial portions of the Software.
//
//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
//THE SOFTWARE.
package tv.dyndns.kishibe.client.util;

import java.util.Comparator;

/**
 * ヒープ構造を実現するクラス
 * 
 * 各メソッドの計算量オーダーはNをインスタンスが保持しているオブジェクトの総数として、 push…O(log(N))、pop…O(log(N))、head…O(1)、remove…O(N)
 * 
 * @author nodchip
 * 
 */
public class Heap {
	/**
	 * Comparatorが指定されなかったときに利用されるデフォルトのComparator。 オブジェクト自身のcompareToを使用する。
	 */
	private static final Comparator DEFAULT_COMPARATOR = new Comparator() {
		public int compare(Object o1, Object o2) {
			return ((Comparable) o1).compareTo(o2);
		}
	};
	/**
	 * オブジェクトを格納する配列の長さの初期値
	 */
	private static final int DEFAULT_INITIAL_CAPACITY = 16;
	/**
	 * オブジェクトの比較で使用するComparator
	 */
	private final Comparator comparator;
	/**
	 * オブジェクトを格納する配列
	 */
	private Object[] objects;
	/**
	 * 保持しているオブジェクトの数
	 */
	private int size = 0;

	/**
	 * デフォルトのComparatorと配列の長さを使用してインスタンスを構築する。
	 */
	public Heap() {
		this(DEFAULT_COMPARATOR, DEFAULT_INITIAL_CAPACITY);
	}

	/**
	 * デフォルトのComparatorと指定された配列の長さを使用してインスタンスを構築する。
	 * 
	 * @param initialCapacity
	 *            オブジェクトを保持する配列の長さの初期値
	 */
	public Heap(int initialCapacity) {
		this(DEFAULT_COMPARATOR, initialCapacity);
	}

	/**
	 * 指定されたComparatorとデフォルトの配列の長さを使用してインスタンスを構築する。
	 * 
	 * @param comparator
	 *            比較に使用するComparator
	 */
	public Heap(Comparator comparator) {
		this(comparator, DEFAULT_INITIAL_CAPACITY);
	}

	/**
	 * 指定されたComparatorと配列の長さを使用してインスタンスを構築する。
	 * 
	 * @param comparator
	 *            比較に使用するComparator
	 * @param initialCapacity
	 *            オブジェクトを保持する配列の長さの初期値
	 */
	public Heap(Comparator comparator, int initialCapacity) {
		this.comparator = comparator;
		objects = new Object[initialCapacity];
	}

	/**
	 * ヒープ構造にオブジェクトを追加する。
	 * 
	 * @param object
	 *            追加するオブジェクト
	 */
	public void push(Object object) {
		int n = ++size;

		// 領域が足りない場合は拡張する
		while (n >= objects.length) {
			expand();
		}

		objects[n] = object;
		toRoot(n);
	}

	/**
	 * ヒープ構造の先頭にあるオブジェクトを返す。取り出されたオブジェクトはヒープ構造から取り除かれる。
	 * 
	 * @return 先頭のオブジェクト
	 */
	public Object pop() {
		Object result = objects[1];

		if (result == null) {
			return null;
		}

		int n = size--;
		objects[1] = objects[n];
		objects[n] = null;
		toLeaf(1);
		return result;
	}

	/**
	 * ヒープ構造の先頭にあるオブジェクトを返す。取り出されたオブジェクトをヒープ構造から取り除かれない。
	 * 
	 * @return 先頭のオブジェクト
	 */
	public Object head() {
		final Object result = objects[1];

		return result;
	}

	/**
	 * ヒープ構造からオブジェクトを取り除く
	 * 
	 * @param object
	 *            取り除くオブジェクト
	 */
	public void remove(Object object) {
		int n = find(object);
		if (n == -1) {
			return;
		}

		objects[n] = objects[size];
		objects[size--] = null;
		toRoot(n);
		toLeaf(n);
	}

	/**
	 * 葉から根に向かってヒープを更新する。
	 * 
	 * @param n
	 *            更新を始める位置を表す配列の添え字
	 */
	private void toRoot(int n) {
		if (objects[n] == null) {
			return;
		}

		int n2;
		while (1 < n && less(objects[n], objects[n2 = n / 2])) {
			swap(n2, n);
			n = n2;
		}
	}

	/**
	 * 根から葉に向かってヒープを更新する
	 * 
	 * @param n
	 *            更新を始める位置を表す配列の添え字
	 */
	private void toLeaf(int n) {
		if (objects[n] == null) {
			return;
		}

		int n2, n21;

		while ((n2 = n * 2) <= size) {
			int nextN = 0;

			// 親より左の子が小さい場合
			if (less(objects[n2], objects[n])) {
				nextN = n2;
			}

			// 親より右の子が小さく、左の子より右の子の方が小さい場合
			if ((n21 = n2 + 1) <= size && less(objects[n21], objects[n]) && less(objects[n21], objects[n2])) {
				nextN = n21;
			}

			if (nextN != 0) {
				swap(n, nextN);
				n = nextN;
			} else {
				break;
			}
		}
	}

	/**
	 * 保持しているComparatorを使用してオブジェクト同士を比較する。operator<()互換。
	 * 
	 * @param o1
	 *            左辺
	 * @param o2
	 *            右辺
	 * @return &lt;が成立すればture
	 */
	private boolean less(Object o1, Object o2) {
		try {
			return comparator.compare(o1, o2) < 0;
		} catch (Exception e) {
			e.printStackTrace();
		}
		return false;
	}

	/**
	 * 配列中のオブジェクトを交換する
	 * 
	 * @param i
	 *            左辺
	 * @param j
	 *            右辺
	 */
	private void swap(int i, int j) {
		Object o = objects[i];
		objects[i] = objects[j];
		objects[j] = o;
	}

	/**
	 * 配列中から線形探索でオブジェクトを探す
	 * 
	 * @param object
	 *            探すオブジェクト
	 * @return オブジェクトの位置。見つからなかった場合は-1を返す。
	 */
	private int find(Object object) {
		for (int i = 1; i <= size; ++i) {
			if (object == objects[i]) {
				return i;
			}
		}

		return -1;
	}

	/**
	 * 配列の長さを拡張する
	 */
	private void expand() {
		Object[] newObjects = new Object[objects.length * 2];
		for (int i = 1; i < objects.length; ++i) {
			objects[i] = newObjects[i];
		}
		objects = newObjects;
	}
}
